package leetcode.interviewClassics;

import leetcode.Hot100.subarraySum;
import leetcode.TreeNode;

import java.util.HashMap;

/**
 * @author Cheng Jun
 * Description: 给定一个二叉树的根节点 root，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
 * <p>
 * 路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/path-sum-iii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @version 1.0
 * @date 2021/12/2 15:41
 * @see subarraySum#subarraySum2(int[], int)
 * 面试题，二刷
 */
public class pathSum3 {
    static int pathNum = 0;

    public static void main(String[] args) {
        TreeNode a = new TreeNode(3);
        TreeNode b = new TreeNode(2);
        TreeNode c = new TreeNode(1, b, a);
        System.out.println(pathSum(c, 1));

    }

    // 这题与 子数组和 很相似，子数组和 中，利用前缀和+HashMap 可以将时间复杂降为 O(n)
    // 这里面 我们先考虑 二叉树的极端情况，只有右子树，那么就可以看做一个链表，就与 子数组和 解法类似，
    // 然后如果该二叉树只有右子树的情况下，倒数第二节点 不仅有 右子树，还有左子树，那么回溯的时候 就要对Hash表 对应的key 做减一。
    static int pathSum(TreeNode root, int targetSum) {
        // key：前缀和 pre  value：pre出现的次数
        HashMap<Integer, Integer> preMap = new HashMap<>();
        // 当node.val 等于 targetSum 时，可以有 0 与之匹配
        preMap.put(0, 1);
        backTrack(root, targetSum, preMap, 0);
        return pathNum;
    }

    static void backTrack(TreeNode node, int targetSum, HashMap<Integer, Integer> preMap, int pre) {
        if (node == null) return;
        // 当前节点不为 null
        pre += node.val;
        int diff = pre - targetSum;
        if (preMap.containsKey(diff)) {
            pathNum += preMap.get(diff);
        } else {

        }
        preMap.put(pre, preMap.getOrDefault(pre, 0) + 1);
        if (node.left != null) {
            backTrack(node.left, targetSum, preMap, pre);
        }

        if (node.right != null) {
            backTrack(node.right, targetSum, preMap, pre);
        }
        // 左右子树处理完，该节点所表示的前缀和 作为key值 对应 preMap的value就要减一，如果这个前缀和只出现一次也没关系。
        preMap.put(pre, preMap.get(pre) - 1);
    }

    // 暴力解法：我们首先想到的解法是穷举所有的可能，我们访问每一个节点 node，
    // 检测以 node 为起始节点且向下延深的路径有多少种。我们递归遍历每一个节点的所有可能的路径，然后将这些路径数目加起来即为返回结果。
    // 不推荐使用暴力解法，时间复杂度O(N^2)
    // 时间复杂度：O(N^2) 空间复杂度：O(N)
    // 其中N 为该二叉树节点的个数。对于每一个节点，求以该节点为起点的路径数目时，则需要遍历以该节点为根节点的子树的所有节点，因此求该路径所花费的最大时间为 O(N)
    // 链接：https://leetcode-cn.com/problems/path-sum-iii/solution/lu-jing-zong-he-iii-by-leetcode-solution-z9td/
    // 暴力解法略

}
